package 力扣_树算法.路径;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 112. 路径总和
 * (二叉树路径类题目挺重要的,也挺有难度)
 * @author zx
 * @create 2022-04-12 16:26
 */
public class Num112 {
    /**
     从根节点开始,每当遇到一个节点的时候,从目标值里扣除节点值,一直到叶子节点判断目标值是不是被扣完。
     递归拆分子问题：
     假定从根节点到当前节点的值之和为 val,是否存在从当前节点的子节点到叶子的路径,满足其路径和为sum - val。
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }






    /**
     * @return 迭代(参考官方)
     * 迭代更难理解
     */
    public boolean hasPathSum2(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        Deque<TreeNode> nodeQueue = new ArrayDeque<>();
        Deque<Integer> pathQueue = new ArrayDeque<>();
        nodeQueue.offer(root);
        pathQueue.offer(root.val);
        while(!nodeQueue.isEmpty()){
            TreeNode node = nodeQueue.poll();
            int sum = pathQueue.poll();
            if(node.left == null && node.right == null){
                if(sum == targetSum){
                    return true;
                }
                //到达此叶子节点的sum不符合,但是还有别的叶子节点
                continue;
            }
            if(node.left != null){
                nodeQueue.offer(node.left);
                pathQueue.offer(node.left.val + sum);
            }
            if(node.right != null){
                nodeQueue.offer(node.right);
                pathQueue.offer(node.right.val + sum);
            }
        }
        return false;
    }

}
